/*
 * LinkedList.h
 *
 *  Created on: Nov 8, 2010
 *      Author: jacob
 */

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include "Node.h"
#include <string>
#include <sstream>
using std::string;
using std::ostringstream;
using std::stringstream;

//Remove me.
#include <iostream>
using std::cout;

template<typename T>
class LinkedList
{
public:
	static LinkedList<T>* newLinkedList();
	void addToHead(T data);
	void addToHead(Node<T>* node);
	void addToTail(T data);
	void addToTail(Node<T>* node);
	bool insert(T data, int position);
	bool insert(Node<T>* node, int position);
	void removeFromHead();
	void removeFromTail();
	bool remove(Node<T>* nodeToBeRemoved);
	Node<T>* search(T nodesValue);
	Node<T>* search(Node<T>* nodeToBeFound);
	Node<T>* getCurrent();
	void sort();
	int getSize();
	string toString();
	LinkedList<T>& operator++();
	virtual ~LinkedList();
private:
	int size;
	Node<T>* head;
	Node<T>* tail;
	Node<T>* current;
	Node<T>* quickSort(Node<T>* node);
	void insertNode(Node<T>* nodeToBeInserted);
	Node<T>* getNodeAtIndex(int nodeIndex);
	Node<T>* constructNewNodeFromData(T data);
	void deleteNode(Node<T>* nodeToBeDeleted);
	void findAndSetTail();
	LinkedList();
};

template<typename T>
LinkedList<T>*
LinkedList<T>::newLinkedList()
{
	return new LinkedList();
}

template<typename T>
LinkedList<T>::LinkedList()
{
	head = NULL;
	tail = NULL;
	current = head;
	size = 0;
}

template<typename T>
LinkedList<T>::~LinkedList()
{
	cout << "\nLinked List Destructor Called: " << this;
	delete head;
}

/*
 * Construsts a node from T and adds to head
 */
template<typename T>
void LinkedList<T>::addToHead(T data)
{
	addToHead(constructNewNodeFromData(data));
}

/*
 * If head is null, sets node to be both head and tail.
 * else it will set head to new head.
 */
template<typename T>
void LinkedList<T>::addToHead(Node<T>* node)
{
	//if no elements, first element added is both head and tail.
	if (head == NULL)
	{
		head = node;
		tail = node;
		size++;
	}
	else
	{
		//else set new element to head.
		node->setNext(head);
		head = node;
		size++;
	}
}

/*
 * Constructs node from data, and adds to tail.
 */
template<typename T>
void LinkedList<T>::addToTail(T data)
{
	addToTail(constructNewNodeFromData(data));
}

/*
 * Will add a node to the tail of the list.
 */
template<typename T>
void LinkedList<T>::addToTail(Node<T>* node)
{
	//before adding head check if tail is null, if so make node head
	//else push to the end of tail.
	if (head == NULL)
	{
		head = node;
	}
	else
		tail->setNext(node);

	tail = node;
	size++;
}

/*
 * Constructs a node from T and inserts it at a given index. Returns if it was successful.
 */
template<typename T>
bool LinkedList<T>::insert(T data, int position)
{
	return insert(constructNewNodeFromData(data), position);
}

/*
 * Searches for index, and inserts if found.
 */
template<typename T>
bool LinkedList<T>::insert(Node<T>* node, int position)
{
	current = head;
	for (int index = 0; index < size; index++)
	{
		if (index == position)
		{
			insertNode(node);
			return true;
		}
		++(*this);
	}
	return false;
}

/*
 * Inserts the node after a given node.
 */
template<typename T>
void LinkedList<T>::insertNode(Node<T>* nodeToBeInserted)
{
	//we already have logic for adding to tail, so do that.
	if (current == tail)
	{
		addToTail(nodeToBeInserted);
	}
	else
	{
		nodeToBeInserted->setNext(current->getNext());
		current->setNext(nodeToBeInserted);
		size++;
	}
}

/*
 * Removes a node from the head.
 */
template<typename T>
void LinkedList<T>::removeFromHead()
{
	//if a head doesn't exist, return
	if (head == NULL)
		return;
	//if one node in the list, delete it, and remove references to it that head and tail have.
	else if (head == tail)
	{
		deleteNode(head);
		head = NULL;
		tail = NULL;
		return;
	}

	//else delete head, and set head to next.
	Node<T>* oldHead = head;
	head = head->getNext();
	deleteNode(oldHead);
}

/*
 * Remove a node from the tail.
 */
template<typename T>
void LinkedList<T>::removeFromTail()
{
	//if there is no tail return
	if (tail == NULL)
		return;
	//if one node in the list, delete it and remove references.
	else if (tail == head)
	{
		deleteNode(tail);
		tail = NULL;
		head = NULL;
		return;
	}

	//Else we should delete tail, and set its predecessor to new tail.
	Node<T>* oldTail = tail;

	current = head;
	for (int index = 0; index < size; index++)
	{
		if (current->getNext() == tail || current == tail)
		{
			tail = current;
			tail->setNext(NULL);
			deleteNode(oldTail);
		}
		++(*this);
	}

}

/*
 * Take a T and creates and returns a node from it.
 */
template<typename T>
Node<T>* LinkedList<T>::constructNewNodeFromData(T data)
{
	return Node<T>::newNodeFromData(data);
}

/*
 * Overload the ++ operator to move down the list.
 */
template<typename T>
LinkedList<T>&
LinkedList<T>::operator++()
{
	current = current->getNext();
	return *this;
}

/*
 * Deletes a node and decrements size.
 */
template<typename T>
void LinkedList<T>::deleteNode(Node<T>* nodeToBeDeleted)
{
	nodeToBeDeleted->setNext(NULL);
	delete nodeToBeDeleted;
	--size;
}

/*
 * Removes a node from the list. Returns whether the node could be found and deleted
 */
template<typename T>
bool LinkedList<T>::remove(Node<T>* nodeToBeRemoved)
{
	//parent of node to be removed.
	Node<T>* last = NULL;

	//Find the node.
	current = head;
	for (int index = 0; index < size; index++)
	{
		if (current->getNext() == nodeToBeRemoved)
		{
			last = current;
			current = current->getNext();
			break;
		}
		++(*this);
	}

	//why rerite, just delete from head if head.
	if (current == head)
	{
		removeFromHead();
		return true;
	}
	//same with tail.
	else if (current == tail)
	{
		removeFromTail();
		return true;
	}
	//remove reference that parent has, and set parents next to nodes next.
	else
	{
		Node<T>* nodeToBeRemoved = current;
		last->setNext(nodeToBeRemoved->getNext());
		deleteNode(nodeToBeRemoved);
		current = head;
		return true;
	}

	return false;

}

/*
 * Searches the list for a specified T value
 */
template<typename T>
Node<T>* LinkedList<T>::search(T nodesValue)
{
	current = head;
	for (int index = 0; index < size; index++)
	{
		if (current->getData() == nodesValue)
		{
			return current;
		}
		++(*this);
	}

	return NULL;
}

/*
 * Searches the list for a specified node
 */
template<typename T>
Node<T>* LinkedList<T>::search(Node<T>* nodeToBeFound)
{
	current = head;
	for (int index = 0; index < size; index++)
	{
		if (current == nodeToBeFound)
		{
			return current;
		}
		++(*this);
	}

	return NULL;
}

template<typename T>
Node<T>* LinkedList<T>::getCurrent()
{
	return this->current;
}

template<typename T>
int LinkedList<T>::getSize()
{
	return this->size();
}

/*
 * Sort the list, then set the tail node.
 */
template<typename T>
void LinkedList<T>::sort()
{
	head = quickSort(head);
	findAndSetTail();
}

template<typename T>
Node<T>* LinkedList<T>::quickSort(Node<T>* node)
{
	//terminates recursion
	if (node == NULL)
		return node;

	Node<T>* left = NULL;
	Node<T>* right = NULL;
	Node<T>* pivot = node;
	Node<T>* incrementer = node->getNext();

	//iterate down each next node.
	while (incrementer != NULL)
	{
		Node<T>* next = incrementer->getNext();

		//if current < put on "list" left
		if (incrementer->getData() < pivot->getData())
		{
			incrementer->setNext(left);
			left = incrementer;
		}
		else // put on "list" right
		{
			incrementer->setNext(right);
			right = incrementer;
		}

		incrementer = next;
	}

	//these return the sorted sublists.
	//sort the left "list"
	left = quickSort(left);
	//sort the right "list"
	right = quickSort(right);

	//put the lower elements before head, since they are sorted and smaller.
	if (left != NULL)
	{
		Node<T>* end = left;

		while (end->getNext() != NULL)
			end = end->getNext();

		end->setNext(pivot);
		pivot->setNext(right);
		return left;
	}
	else //put the higher elements after pivot.
	{
		pivot->setNext(right);
		return pivot;
	}

}

/*
 * Searches the list and tries to return a node at a given index
 */
template<typename T>
Node<T>* LinkedList<T>::getNodeAtIndex(int nodesIndex)
{
	current = head;
	for (int index = 0; index < size; index++)
	{
		if (index == nodesIndex)
		{
			return current;
		}
		++(*this);
	}
}

/*
 * Finds the tail, and sets the tail pointer to this.
 * This is needed because tail is lost during sorting.
 */
template<typename T>
void LinkedList<T>::findAndSetTail()
{
	current = head;
	for (int index = 0; index < size; index++)
	{
		if (current->getNext() == NULL)
		{
			tail = current;
		}
		++(*this);
	}
}


/*
 * Summary: Print the linked list, in this case multiple entries per row.
 */
template<typename T>
string LinkedList<T>::toString()
{
	ostringstream stringStream;
	string newLine = "\n=-=-=-=-=-=-=-=-=-=-=-=-=-=-=";

	stringStream << newLine << "\nLinked List: Size: " << size << newLine;

	int numberPerRow = 5;
	int currentNumberInRow = 0;

	//print rows and colums for data
	current = head;
	for (int index = 0; index < size; index++)
	{
		if (currentNumberInRow == numberPerRow)
			currentNumberInRow = 0;

		if (currentNumberInRow == 0)
			stringStream << "\n";
		stringStream << current->getData() << "  ";

		++(*this);
		currentNumberInRow++;
	}

	stringStream << newLine;

	//if there is a head and tail, print those values.
	if (head != NULL && tail != NULL)
	{
		stringStream << "\n" << "Head: " << head->getData();
		stringStream << "\n" << "Tail: " << tail->getData();
	}
	//else print their pointers
	{
		stringStream << "\n" << "Head: " << head;
		stringStream << "\n" << "Tail: " << tail;
	}
	//output the size.
	stringStream << newLine << "\nLinked List: Size: " << size;
	stringStream << newLine;

	return stringStream.str();
}

#endif /* LINKEDLIST_H_ */
